import javafx.util.Pair;

import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {

    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.add(new Pair<>(root, 1));
        int ret = 0;
        while(!queue.isEmpty()){
            int sz = queue.size();
            //更新ret
            Pair<TreeNode, Integer> peek = queue.peek();//队头
            Pair<TreeNode, Integer> tail = ((LinkedList<Pair<TreeNode, Integer>>)queue).getLast();//获取队尾
            ret = Math.max(tail.getValue() - peek.getValue() + 1, ret);
            for(int i = 0; i < sz; i++){
                Pair<TreeNode, Integer> poll = queue.poll();
                TreeNode partent = poll.getKey();
                //
                if(partent.left != null){
                    queue.add(new Pair<>(partent.left, poll.getValue() * 2));
                }
                if(partent.right != null){
                    queue.add(new Pair<>(partent.right, poll.getValue() * 2 + 1));
                }
            }
        }
        return ret;
    }
}